package com.weic.algorithm.order;

/**
 * 排序算法类
 */
public class MyOrder {


    /**
     * 选择排序
     * 思路：从一组数据中选出最小的一个元素放置在第i位上
     * @param arr
     */
    public void selectOrder(int[] arr){
        //确认边界
        if(null == arr || arr.length<2){
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int currentIdx = i;
            for (int j = i+1; j < n; j++) {
                if(arr[currentIdx]> arr[j]){
                    currentIdx = j;
                }
            }
            if(i!=currentIdx){
                swap(arr,i,currentIdx);
            }
        }
    }

    /**
     * 插入排序
     * 思路：从第二个元素开始，之前的元素序列有序（因为只有一个元素），将当前值依次和前面的数据做比较，若小于则位置兑换
     * @param arr
     */
    public void insertOrder(int[] arr){
        //确认边界
        if(null == arr || arr.length<2){
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j >0; j--) {
                if(arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }else{
                    break;
                }

            }
        }
    }


    /**
     * 冒泡排序
     * 思路：相邻元素进行比较，大的元素往后置换位置
     * @param arr
     */
    public void bubbleOrder(int[] arr){
        //确认边界
        if(null == arr || arr.length<2){
            return;
        }
       int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    /**
     * 数据交换逻辑
     * @param arr
     * @param idx1
     * @param idx2
     */
    private void swap(int[] arr,int idx1,int idx2){
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}
